package a.codetop.单调栈;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class 每样一个字典序最小_316 {

    @Test
    public void test() {
        System.out.println(removeDuplicateLetters("cbacdcbc"));
    }
    public String removeDuplicateLetters(String s) {
        char[] chars = s.toCharArray();
        Set<Character> set = new HashSet<>();
        Stack<Character> stack = new Stack<>();

        for (char c:chars){
            //栈空直接压
            if(stack.isEmpty()){
                stack.push(c); set.add(c);
            }
            //栈不空
            else{
                //只有是新的不存在的字符，才可以用‘小的向前顶’
                if(!set.contains(c)) {
                    while (!stack.isEmpty() && c < stack.peek()) {
                        Character top = stack.pop(); set.remove(top);
                    }
                    stack.push(c);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < stack.size(); i++) {
            sb.append(chars[i]);
        }
        return sb.toString();
    }
}
